class Solution
{
public:
    vector<int> cycleLengthQueries(int n, vector<vector<int>> &queries)
    {
        // 找到最近公共祖先即可
        auto doQuery = [](int node1, int node2) -> int
        {
            stack<int> node1Parents;
            stack<int> node2Parents;
            while (node1 > 0)
            {
                node1Parents.push(node1);
                node1 /= 2;
            }
            while (node2 > 0)
            {
                node2Parents.push(node2);
                node2 /= 2;
            }
            while (!node1Parents.empty() && !node2Parents.empty())
            {
                if (node1Parents.top() == node2Parents.top())
                {
                    node1Parents.pop();
                    node2Parents.pop();
                }
                else
                {
                    break;
                }
            }
            return node1Parents.size() + node2Parents.size() + 1;
        };
        vector<int> result;
        for (auto &query : queries)
        {
            result.push_back(doQuery(query[0], query[1]));
        }
        return result;
    }
};